With regard to data networking, a class of switching systems most commonly implemented today relies on particular schemes of input queueing as well as output queueing to achieve a high throughput non-blocking switching architecture. Input queueing, otherwise known as ingress scheduling, refers to scheduling into the switching fabric of a switching system. On the other hand, output queueing refers to scheduling onto the network on the system egress ports. In both cases, a finite memory space is used to hold packets before they get the chance to be transmitted out into the fabric or out to the network. Memory is often managed (allocated and freed) in fixed segments of bytes called buffers. A buffer is used to store data-packet segments and some sort of header that describes different characteristics of the data (e.g., destination, drop probability, position in the packet etc.)
An N×N switching fabric 10 can be logically represented as a black box with N input ports 12 and N output ports 14 as depicted in FIG. 1. The input and output ports are of equal speeds. The switch fabric arbitrates which input port gets to transmit to which output port at a given point in time. This arbitration is also referred to as fabric scheduling. There are multiple problems that may arise in such a system that mandate a good queueing architecture and a good buffer management scheme to reduce data loss and achieve fairness across ports. On the ingress side, for instance, it is possible that data packets simultaneously arrive on multiple input ports and they are destined to the same output port. Since input and output ports have equal speeds, this situation gives rise to output port congestion and packets will have to be buffered at the ingress of the fabric before they have the chance to be switched to the output port. In addition, packets destined to other egress ports may arrive on the same input port. It is important in this case that the packets destined to the congested output port do not block the packets destined to output ports that are not congested.
To avoid this kind of head-of-line (HOL) blocking, a set of N virtual output queues (VOQ's) 20 is usually implemented in each ingress port for each traffic class (FIG. 2). Thus, at a given input port 22, buffer space must be intelligently allocated for packets in different VOQ's. In a similar manner, on the egress side, a switch fabric port may branch out to several network ports of lower speed. In this case, an egress fabric port 24 acts as input to the M egress network ports 26 as shown in FIG. 2. Because of the speed difference between the switch fabric port and the network ports, packets may need to be buffered up momentarily and a fair and efficient algorithm is required to allocate buffer space to different network ports. For ease of discussion, in the rest of the document, both the ingress VOQ's and the egress port queues will be denoted simply as queues. The meaning of queues will depend on whether the buffer management scheme is used in the ingress or in the egress.
In a communication queueing system, it is often the case that not all data packets receive the same treatment. This is true in networking technologies that support Quality of Service (QoS) such as Asynchronous Transport Mode (ATM) and Differentiated Services (DS) in the Internet Protocol (IP). Thus, it is important to guarantee more assurance of packet delivery to more important packets. Service classes, and therefore packets that belong to them, can be ordered in terms of importance. Within a service class, some packets can be assigned a higher drop probability or loss probability than others making them less important to be delivered. Thus, it is important to manage the buffer space so that more important packets get more access to buffer space than less important packets.
Complete buffer sharing between different queues allows the available buffers to be used more efficiently and potentially leads to higher throughput and lower data loss probability. If buffers are statically allocated to queues, idle queues (i.e. queues that do not receive any data packets) will not use their allocated buffer space while filled or congested queues will see a high drop probability. If buffer sharing is allowed, a queue will be allowed to use more of the available buffer space thus reducing the drop probability. However, sharing can lead to one set of queues (even one queue) starving other queues of buffer space. Accordingly, there is a need for an improved buffer management technique that improves upon those deficiencies existing in the prior art.